1521. Оптимальное умножение матриц - 2

 

Имея две матрицы A и B, мы можем вычислить C = AB, используя стандартные правила умножения матриц:

Число колонок в матрице A должно совпадать с числом строк матрицы B. Пусть матрица A имеет размер m × n, матрица B имеет размер n × p. Тогда матрица С будет иметь размер m × p, а для ее вычисления следует совершить m * n * p умножений.

Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то необходимо совершить 10 × 20 × 15 = 3000 умножений для вычисления матрицы C.

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы X, Y и Z, то вычислить XYZ можно либо как (XY)Z, либо как X(YZ). Пусть X имеет размер  5 × 10, Y имеет размер 10 × 20, Z имеет размер 20 × 35.

Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

 

(XY)Z

·        5 × 10 × 20 = 1000 умножений для определения матрицы (XY), имеющей размер 5 × 20.

·        Потом 5 × 20 × 35 = 3500 умножений для нахождения конечного результата.

·        Общее количество умножений: 4500.

 

X(YZ)

·        10 × 20 × 35 = 7000 умножений для определения матрицы (YZ), имеющей размер 10 × 35.

·        Потом  5 × 10 × 35 = 1750 умножений для нахождения конечного результата.

·        Общее количество умножений: 8750.

 

Очевидно, что при вычислении (XY)Z требуется меньшее количество умножений.

 

По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

 

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество n (n ≤ 10) перемножаемых матриц. Далее следуют n пар целых чисел, описывающих количество строк и столбцов в матрице, размеры матриц задаются в порядке их перемножения. Последний тест содержит n = 0 и не обрабатывается.

 

Выход. Пусть матрицы пронумерованы A1, A2,..., An. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются, начиная с 1. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

 

Пример входа

Пример выхода

3

1 5

5 20

20 1

3

5 10

10 20

20 35

6

30 35

35 15

15 5

5 10

10 20

20 25

0

Case 1: (A1 x (A2 x A3))

Case 2: ((A1 x A2) x A3)

Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))

 

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Обозначим через Aij произведение матриц Ai * Ai+1 * … * Aj-1 * Aj (1 £ i £ j £ n), через    m[i, j] минимальное количество умножений, необходимое для вычисления Aij. Стоимость вычисления всего произведения A1n будет храниться в m[1, n]. Значения m[i, i] = 0, поскольку Aii = Ai и для его нахождения вычисления не нужны.

Количество столбцов матрицы Ai равно количеству строк матрицы Ai+1. Это значение хранится в p[i]. Количество строк матрицы А1 находится в p[0], а количество столбцов An – в p[n].

Предположим, что при оптимальной расстановке скобок в произведении Ai * … * Aj последней операцией умножения будет (Ai * … * Ak ) * (Ak+1 * … * Aj). Значение m[i, j] равно сумме минимальной стоимости вычислений Aik и Ak+1j плюс стоимость умножения этих двух матриц:

m[i, j] = m[i, k] + m[k + 1, j] + p[i – 1] * p[k] * p[j]

При этом число k может принимать только j – i разных значений: i, i + 1, …, j – 1. Поскольку только одно из них является оптимальным, то необходимо перебрать все эти значения и выбрать наилучшее. Получим рекуррентную формулу:

m[i, j] =

Для запоминания оптимального умножения положим s[i, j] = k, если при оптимальном вычислении Ai * … * Aj последней операцией будет умножение Ai * … * Ak на Ak+1 * … * Aj.

 

Пример

Рассмотрим третий тест. Данные о размерах входных матриц сохраняются в массиве p:

 

 

Минимальная стоимость вычисления матриц Aij хранится в ячейках массива m[i, j]:

 

 

Соответствующие значения матрицы s:

 

 

Для умножения шести входных матриц достаточно выполнить m[1,6] = 15125 операций  умножения. Оптимальная последовательность умножений имеет вид:

A16 = (s[1,6] = 3) = A13 * A46 =

(s[1,3] = 1, s[4,6] = 5) = (A11 * A23) * (A45 * A66) =

(s[2,3] = 2, s[4,5] = 4) = (A11 * (A22 * A33 ) ) * ((A44 * A55) * A66) =

(A1 * (A2 * A3 ) ) * ((A4 * A5) * A6)

 

Реализация алгоритма

Переменная INF обозначает число «бесконечность», MAX – 1 содержит максимально возможное число матриц в произведении. Объявим строковый массив Stroka, в котором храним числа от 0 до 10 в виде строк. Объявим массивы m, s, p, описанные выше. В переменной Answer будем накапливать результат.

 

#define INF 0x3F3F3F3F3F3F3F3F

#define MAX 11

string Stroka[11] = {"0","1","2","3","4","5","6","7","8","9","10"};

long long m[MAX][MAX], s[MAX][MAX], p[MAX];

string Answer;

 

Функция Mult находит минимальное количество умножений, необходимое для вычисления Aij = Ai * Ai+1 * … * Aj-1 * Aj, которое сохраняем в ячейке m[i, j].

 

long long Mult(int i, int j)

{

  if (m[i][j] == INF)

    for (int k = i; k <= j - 1; k++)

    {

      long long temp = Mult(i,k) + Mult(k+1,j) + p[i-1] * p[k] * p[j];

      if (temp < m[i][j])

      {

        m[i][j] = temp; s[i][j] = k;

      }

    }

  return m[i][j];

}

 

Функция Print(i, j) выводит оптимальное произведение матриц Ai * Ai+1 * … * Aj-1 * Aj согласно формату вывода.

 

string Print(int i, int j)

{

  if (i == j) return "A" + Stroka[i];

  return "(" + Print(i,s[i][j]) + " x " + Print(s[i][j]+1,j) + ")";

}

 

Основной цикл программы. Переменная cs содержит номер теста.

 

cs = 1;

while(scanf("%d",&n),n)

{

 

Присвоим всем ячейкам массива m значения «бесконечность».

 

  memset(m,0x3F,sizeof(m));

 

Читаем размеры входных матриц, сохраняем их в массиве p. Положим m[i, i] = 0.

 

  for(i = 1; i <= n; i++)

  {

    scanf("%d %d",&p[i-1],&p[i]); m[i][i] = 0;

  }

 

Вычисляем результат – ищем оптимальное произведение матриц A1 * A2 * … * An-1 * An.

 

  Mult(1,n);

 

Выводим номер теста cs. Если n = 1, то перемножать нечего и следует вывести строку "(A1)". Иначе вызываем функцию Print(1,n), которая возвращает строку, содержащую последовательность оптимального произведения матриц.

 

  printf("Case %d: ",cs++);

  if (n == 1) Answer = "(A1)"; else Answer = Print(1,n);

 

Выводим результат – строку Answer.

 

  printf("%s\n",Answer.c_str());

}